package com.lenl.datastruct.stack;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-04-29 11:15
 * @description 栈实现计算器
 */
public class Calculator {
    public static void main(String[] args) {
        //表达式运算
        String expression = "130+2*11-3";
        //创建两个栈，数栈，符号栈
        ArrayStack2 numStack=new ArrayStack2(10);
        ArrayStack2 operStack=new ArrayStack2(10);
        //定义需要的相关变量
        int index=0;//用于扫描
        int num1=0;
        int num2=0;
        int oper=0;
        int res=0;
        char ch=' ';//将每次扫描到的char保存到ch
        String keepNum="";
        //开始while循环扫描expression
        while(true){
            //依次得到expression的每一个字符
            ch=expression.substring(index,index+1).charAt(0);
            //判断数字或符号
            if(operStack.isOper(ch)){
                //运算符
                //判断当前符号栈是否为空
                if(!operStack.isEmpty()){
                    if(operStack.priority(ch)<=operStack.priority(operStack.peek())){
                        num1=numStack.pop();
                        num2=numStack.pop();
                        oper=operStack.pop();
                        res=numStack.cal(num1,num2,oper);
                        numStack.push(res);
                        operStack.push(ch);
                    }else{
                        operStack.push(ch);
                    }
                }else{
                    operStack.push(ch);
                }
                //让index+1，并判断是否扫描到expression最后
                index++;
            }else{
                //如果是数，直接入数栈
                //多数要往后看
                keepNum+=ch;
                index++;
                //判断后面的字符
                while (true){
                    if(index+1>expression.length())
                        break;
                    String ex=expression.substring(index,index+1);
                    if(!operStack.isOper(ex.charAt(0))){
                        keepNum+=ex;
                        index++;
                    }else{
                        break;
                    }
                } 
                numStack.push(Integer.parseInt(keepNum));
                keepNum="";

            }

            if(index>=expression.length())
                break;
        }
        //顺序从数栈和符号栈取出相应的数和符号，并计算，最后留在数栈中的为结果
        while (true){
            //如果符号栈为空，则计算到最后的结果，数栈中只有结果
            if(operStack.isEmpty()){
                break;
            }
            num1=numStack.pop();
            num2=numStack.pop();
            oper=operStack.pop();
            res=numStack.cal(num1,num2,oper);
            numStack.push(res);
        }
        //数栈最后一个数解释结果
        int result=numStack.pop();
        System.out.println(expression+"结果为："+result);


    }
}

//定义一个ArrayStack标识栈
class  ArrayStack2{
    private int maxSize;//栈大小
    private  int[] stack;//数据存储
    private  int top=-1; //栈顶，初始-1
    //构造器
    public ArrayStack2(int maxSize){
        this.maxSize=maxSize;
        stack=new int[maxSize];
    }
    //peek栈顶的值
    public  int peek(){
        if(!isEmpty()){
            return stack[top];
        }else{
            System.out.println("栈为空");
            throw new RuntimeException("栈为空");
        }
    }

    //栈满
    public boolean isFull(){
        return top==maxSize-1;
    }
    //栈空
    public  boolean isEmpty(){
        return top==-1;
    }
    //入栈 push
    public void push(int value){
        if(isFull()){
            System.out.println("栈满");
            return;
        }
        top++;
        stack[top]=value;
    }
    //出栈 pop
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("栈空，无数据");
        }
        int val=stack[top];
        top--;
        return val;
    }
    //遍历栈
    public void list(){
        //需要从栈顶开始显示数据
        if(isEmpty()){
            System.out.println("栈空，无数据");
            return;
        }
        for(int i=top;i>=0;i--){
            System.out.println("stack["+i+"]="+stack[i]);
        }
    }

    //返回运算符的优先级（由程序员定）,使用数字标识，越大越高
    public int priority(int oper){
        if(oper=='*'||oper=='/'){return 1;}
        else if(oper=='+'||oper=='-'){
            return 0;
        }else{
            return -1;//非加减乘除
        }
    }
    //判断是不是一个运算符
    public boolean isOper(char val){
        return val=='+'||val=='-'||val=='*'||val=='/';
    }
    //计算方法
    public int cal(int num1,int num2,int oper){
        int res=0;//返回结果
        switch(oper){
            case '+':
                res=num2+num1;
                break;
            case  '-':
                res=num2-num1;
                break;
            case '*':
                res=num2*num1;
                break;
            case '/':
                res=num2/num1;
                break;
            default:
                break;
        }
        return res;
    }

}